#define _CRT_SECURE_NO_WARNINGS 1

#include <list>
#include <map>
#include <iostream>
#include "Widget.hpp"

//int main()
//{
//	std::list<ListNode_T<int>*> l;
//	std::map<int, MapNode_T<int>*> m;
//
//	Widget<int> w(10);
//	l.push_back(w._ln);
//	m.insert(std::make_pair(1, w._mn));
//
//	auto it = m.find(1);
//	if (it != m.end()) {
//		std::cout << (it->second->_OwnNode)->_val << std::endl;
//	}
//
//	for (auto& e : l) {
//		std::cout << e->_OwnNode->_val << std::endl;
//	}
//}

#include <string>

using namespace std;

class Solution {
public:
    bool checkInclusion(string s1, string s2)
    {
        int hashS1[26] = { 0 };
        int hashWindow[26] = { 0 };
        int cntS1 = 0, cntWindow = 0;
        int left = 0, right = 0;
        // init
        for (int i = 0; i < s1.size(); ++i) {
            if (hashS1[s1[i] - 'a'] == 0) { ++cntS1; }
            hashS1[s1[i] - 'a']++;
        }
        while (right < s2.size())
        {
            // in
            hashWindow[s2[right] - 'a']++;
            if (hashWindow[s2[right] - 'a'] == hashS1[s2[right] - 'a']) {
                ++cntWindow;
            }
            // judge
            if (right - left + 1 == s1.size()) {
                if (cntS1 == cntWindow) {
                    return true; // return
                }
                // out
                if (hashWindow[s2[left] - 'a'] == hashS1[s2[left] - 'a']) {
                    --cntWindow;
                }
                hashWindow[s2[left++] - 'a']--;
            }
            ++right;
        }
        return false;
    }
};

int main()
{
    Solution().checkInclusion("ab", "eidboaoo");
    return 0;
}